/**
 * 
 */
package Prim;
import java.util.*;
/**
 * @author 41051267
 *
 */
public class Prim {

	public static final int inf= Integer.MAX_VALUE;
	private double [][] M;
	private int pi[]; // predecessor
	private int n; // regulagem do vetor
	private double key[];
	private int origem;
	private int [] Q;

	public Prim(double M[][],int origem) {
		this.M = M;
		n=M.length;
		pi=new int[n];
		key=new double[n];
		this.origem=origem;
		prim();
	}
	
	private int extractMin(int vetor[]){
		int menor=0,j=0;
		while(j<n && Q[j]==1) //procura pelo menor que nao faca parte de Q
				j++; 
		menor=j;
		for(int i=1;i<key.length;i++ )
			if(vetor[i] == 0 && key[i] < key[menor])
				menor=i;
		vetor[menor]=1;
		return menor;
	}

	public void prim() {
		
		Q=new int [n];
		for(int i=0;i<key.length;i++) {
			key[i]=Integer.MAX_VALUE;
			Q[i]=0;
		}

		key[origem]=0;
		pi[origem]=-1;
		while(n>=0) {
			int u = extractMin(Q);
			//System.out.println(u);
			for( int v=0; v<M.length; v++)
				if(M[u][v] < inf && Q[v]==0 && M[u][v] < key[v]) { //&& M[u][v] < inf
					pi[v]=u;
					key[v]=M[u][v];
				}
			n--;
		}
		path();
	} // prim

	public void path() {
		System.out.println("Antecessores");
		for(int i=0;i<M.length;i++) System.out.print(i+"\t");
		System.out.println();
		for(int i: pi) 	System.out.print(i+"\t");
		System.out.println();
//		for(double i: key) 	System.out.print(i+" ");
//		System.out.println();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		double M [][]= {
			{inf,337,1846,1464,2704,inf,inf,inf,inf}, //A
			{337,inf,inf,1235,inf,inf,2342,inf,inf}, //B
			{1846,inf,inf,2704,867,749,inf,621,849}, // C
			{1464,1235,2704,inf,inf,1391,1121,inf,inf}, //D
			{inf,inf,867,inf,inf,187,1258,inf,inf}, //E
			{inf,inf,740,1391,187,inf,inf,184,144}, //F
			{inf,2342,inf,1121,1258,inf,inf,946,inf}, //G
			{inf,inf,621,inf,inf,184,946,inf,inf}, //H
			{inf,inf,846,inf,inf,144,inf,inf,inf} //I
		};	
		new Prim(M,7);
	}

}
